package com.leetcode.partition14;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2022/2/6 17:56
 */
public class LC1349参加考试的最大学生数 {

    private static final int N = 10, M = 10;
    private static int[] graph = new int[N];
    //f[i][j]表示考虑前i行，且当前行的状态是j的情况下能安排的最大学生数量
    private static int[][] f = new int[N][1 << M];
    private static Map<Integer, List<Integer>> stm = new HashMap<>();

    private static int n = 0, m = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
        char[][] seats = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = reader.readLine();
            for (int j = 0; j < m; j++) seats[i][j] = s.charAt(j);
        }
        writer.write(maxStudents(seats) + "\n");
        writer.flush();
    }

    public static int maxStudents(char[][] seats) {
        n = seats.length;
        m = seats[0].length;
        init(seats);
        for (int i = 1; i <= n + 1; i++) {
            for (Map.Entry<Integer, List<Integer>> entry : stm.entrySet()) {
                int cur = entry.getKey(), cnt = bitCount(cur, m);
                if ((cur & graph[i]) == 0) {
                    for (int pre : entry.getValue()) {
                        f[i][cur] = Math.max(f[i][cur], cnt + f[i - 1][pre]);
                    }
                }
            }
        }
        return f[n + 1][0];
    }

    private static void init(char[][] seats) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i + 1] |= (seats[i][j] == '#' ? 1 : 0) << j;
            }
        }
        //预处理出单行合法的状态
        for (int i = 0; i < 1 << m; i++) {
            if ((i & (i << 1)) == 0) stm.put(i, new ArrayList<>());
        }
        //在当前行合法的基础上，预处理出上一行的合法状态
        for (Map.Entry<Integer, List<Integer>> entry : stm.entrySet()) {
            int cur = entry.getKey();
            List<Integer> stv = entry.getValue();
            for (int pre : stm.keySet()) {
                int st = cur | pre;
                if ((st & (st << 1)) == 0) stv.add(pre);
            }
        }
    }

    private static int bitCount(int num, int n) {
        int res = 0;
        for (int i = 0; i < n; i++) res += num >> i & 1;
        return res;
    }
}
